package 递归回溯.二维版;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 本题实现有多种方式
 * 1.深度||广度
 * 2.边缘查法(复用性不高,就不考虑)
 * 3.并查集(挺高级的)
 */
public class No130被围绕的区域 {

    /**
     * 给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
     * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     *
     * 示例:
     * X X X X
     * X O O X
     * X X O X
     * X O X X
     * 运行你的函数后，矩阵变为：
     * X X X X
     * X X X X
     * X X X X
     * X O X X
     */

    private char[][] arr;
    private boolean[][] flag;
    private int allLength;
    private int itemLength;
    //上右下左
    private int[][] around={{-1,0},{0,1},{1,0},{0,-1}};

    public void solve(char[][] board) {
        if(board.length==0)
            return;
        /**
         * 两个for去找o元素,找到后对o元素进行扩散,每个元素都检验上下左右,一个节点ok就继续dg,否则返回false
         */
        this.arr=board;
        this.allLength=board.length;
        this.itemLength=board[0].length;
        this.flag=new boolean[allLength][itemLength];
        Deque<Integer> queue=new ArrayDeque<>();
        List<Integer> path=new ArrayList<>();
        for (int i = 0; i < allLength; i++) {
            for (int j = 0; j < itemLength; j++) {
                //O元素&&未探索
                if(arr[i][j]=='O'&&!flag[i][j]){
                    boolean bfs = bfs(i, j, queue, path);
                    if(bfs){
                        for (int k = 0; k < path.size(); k++) {
                            int newX=path.get(k)/itemLength;
                            int newY=path.get(k)%itemLength;
                            arr[newX][newY]='X';
                        }
                    }
                    path.clear();
                    queue.clear();
                }
            }
        }
    }

    //广度优先好,一次检验完一个节点
    private boolean bfs(int startX,int startY,Deque<Integer> queue,List<Integer> path){

        boolean thisFlag=true;
        // 5 7
        //2,5->19   解->x:19/7=2 y:19%7=5
        queue.addLast(startX*itemLength+startY);
        path.add(startX*itemLength+startY);

        while (!queue.isEmpty()){
            Integer removeFirst = queue.removeFirst();
            flag[startX][startY]=true;
            for (int i = 0; i < 4; i++) {
                int newX=removeFirst/itemLength+around[i][0];
                int newY=removeFirst%itemLength+around[i][1];
                //未边界&&下一节点为O&&未探索
                if(newX>=0&&newX<=allLength-1&&newY>=0&&newY<=itemLength-1
                        &&arr[newX][newY]=='O'&&!flag[newX][newY]){
                    //下一个节点是O才继续递归
                    flag[newX][newY]=true;
                    queue.addLast(newX*itemLength+newY);
                    path.add(newX*itemLength+newY);
                    //是广度,所以这里无需递归
                }else if (newX<0||newX>=allLength||newY<0||newY>=itemLength){
                    //已经到了边界,但是先让它全部标记完,不直接返回
                    thisFlag=false;
                }else{
                    //什么都不做
                    System.out.println("not thing");
                }
            }
        }
        return thisFlag;
    }

    //再来一种厉害的解法:并查集式->前往并查集文件夹

    @SuppressWarnings("all")
    public static void main(String[] args) {
        char[][] arr=
               {{'X','O','O','X','X','X','O','X','O','O'},
                {'X','O','X','X','X','X','X','X','X','X'},
                {'X','X','X','X','O','X','X','X','X','X'},
                {'X','O','X','X','X','O','X','X','X','O'},
                {'O','X','X','X','O','X','O','X','O','X'},
                {'X','X','O','X','X','O','O','X','X','X'},
                {'O','X','X','O','O','X','O','X','X','O'},
                {'O','X','X','X','X','X','O','X','X','X'},
                {'X','O','O','X','X','O','X','X','O','O'},
                {'X','X','X','O','O','X','O','X','X','O'}};
        No130被围绕的区域 n=new No130被围绕的区域();
        n.solve(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
